package leecode

func subarraysDivByK(nums []int, k int) (result int) {
	prefix := make([]int, len(nums)+1)
	for i := 0; i < len(nums); i++ {
		prefix[i+1] = prefix[i] + nums[i]
	}
	//1.同余定理
	// if   (a-b)%k == 0
	// 则    a % k == b % k
	//2.修正(是种“映射”)  <暂时当作结论：细节太多>记住 (a%p+p)%p
	hashMap := make(map[int]int)
	for i := 0; i < len(prefix); i++ {
		// 计算当前位置的前缀和对 k 取余
		remainder := (prefix[i]%k + k) % k
		result += hashMap[remainder]
		//存入hash表当前key,即余数
		hashMap[remainder]++
	}
	return
}
